package trees;

import beans.TreeNode;

/**
 * @author pengfei.hpf
 * @date 2020/2/7
 * @verdion 1.0.0
 *
 * The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
 *
 * Determine the maximum amount of money the thief can rob tonight without alerting the police.
 *
 * Example 1:
 *
 * Input: [3,2,3,null,3,null,1]
 *
 *      3
 *     / \
 *    2   3
 *     \   \
 *      3   1
 *
 * Output: 7
 * Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
 * Example 2:
 *
 * Input: [3,4,5,1,3,null,1]
 *
 *      3
 *     / \
 *    4   5
 *   / \   \
 *  1   3   1
 *
 * Output: 9
 * Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RobIII {
    public int rob(TreeNode root){
        if(root == null){
            return 0;
        }
        int[] result = robHouse(root);
        return Math.max(result[0], result[1]);
    }

    private int[] robHouse(TreeNode root){
        if(root == null){
            return new int[2];
        }
        int[] leftV = new int[2];
        int[] rightV = new int[2];
        if(root.left != null){
            leftV = robHouse(root.left);
        }
        if(root.right != null){
            rightV = robHouse(root.right);
        }
        int[] result = new int[2];
        result[0] = Math.max(leftV[0], leftV[1]) + Math.max(rightV[0], rightV[1]);
        result[1] = root.val + leftV[0] + rightV[0];
        return result;
    }
}
